'''
https://leetcode.cn/problems/binary-tree-cameras/
'''
from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        # returns:
        #   1当前没有被覆盖
        #   2当前被覆盖了，当前身上没有摄像头
        #   3当前被覆盖了，当前身上有摄像头
        def f(root):
            if not root:
                return float('inf'), 0, float('inf')
            l_uncovered, l_covered_no_camera, l_covered_has_camera = f(root.left)
            r_uncovered, r_covered_no_camera, r_covered_has_camera = f(root.right)
            # 当前不被覆盖，左右都不能有摄像头, 且左右必须得覆盖了，因为没人在帮他们cover了
            uncovered = l_covered_no_camera + r_covered_no_camera
            # 左右最少有一个摄像头
            covered_no_camera = min(
                l_covered_has_camera + r_covered_has_camera,
                l_covered_has_camera + r_covered_no_camera,
                l_covered_no_camera + r_covered_has_camera,
            )
            # 左右无所谓9种情况都枚举,可以剪枝
            covered_has_camera = 1 + min(
                l_uncovered + r_uncovered,
                l_uncovered + r_covered_no_camera,
                l_uncovered + r_covered_has_camera,
                l_covered_no_camera + r_uncovered,
                l_covered_no_camera + r_covered_no_camera,
                l_covered_no_camera + r_covered_has_camera,
                l_covered_has_camera + r_uncovered,
                l_covered_has_camera + r_covered_no_camera,
                l_covered_has_camera + r_covered_has_camera,
            )
            return uncovered, covered_no_camera, covered_has_camera

        root_uncovered, root_covered_no_camera, root_covered_has_camera = f(root)
        return min(root_uncovered + 1, root_covered_no_camera, root_covered_has_camera)